A "reasoning system" as used herein is a system comprising rules structured to simulate a particular reasoning process. "Real-time" as used herein means the actual time in which an event takes place with the reporting on or recording of the event being practically simultaneous with the occurrence of the event.
Reasoning systems generally include a knowledge base. The knowledge base is a software model of the reasoning methodologies of one or more experts, usually elicited through extensive questioning. During development of a rule-based knowledge base, i.e. development of rule conclusions and rule predicates which comprise the rules of the knowledge base, data is input to the system and the system conclusions are compared with the expert conclusions. If a difference exits between the system and expert conclusions, then the rule conclusions and/or rule predicates are modified so that the system conclusions are in accord with the expert conclusions.
A reasoning system related to the present invention is described in allowed U.S. patent application Ser. No. 103,465, filed Oct. 1, 1987, entitled "A Reasoning System for Reasoning with Uncertainty", now U.S. Pat. No. 4,860,213, which is assigned to the present assignee and incorporated herein, in its entirety, by reference. The reasoning system described in the above-identified patent application, among other features, determines the degree to which a rule premise of a given rule has been satisfied, propagates an amount of uncertainty through the firing of a given rule, summarizes findings provided by various rules or knowledge sources, and detects inconsistencies among different sources of knowledge.
The reasoning system described in U.S. patent application Ser. No. 103,465 includes a knowledge base, a representation portion, a control portion and an inference portion. Specifically, the knowledge base comprises a plurality of system rules each having a premise and a conclusion. The rule premise comprises at least one clause including a variable to which a value can be assigned. In order to determine the total effect of a change-in-state of one variable, each rule of the knowledge base must be scanned to determine whether the clause of its rule premise includes that variable. After each affected rule is identified, then the rules are fired and a conclusion is determined.
The representation portion described in the above-identified patent application generates a value certainty interval associated with each value assigned to each rule premise variable, the value certainty interval having a lower and an upper bound respectively representative of amounts of confirmation and failure of refutation of the assigned value. The representation portion additionally represents to the user a sufficiency factor and a necessity factor associated with each rule. The sufficiency factor represents a strength of belief that the rule conclusion is true given the rule premise is true. The necessity factor represents a strength of belief that the rule conclusion is false given the rule premise is false. The control portion selects computational functions in accordance with which the value certainty interval associated with each assigned value is propagated through the system.
The inference portion described in the above-identified patent application computes a premise certainty interval from the value certainty intervals respectively associated with the values assigned to the premise clauses. A lower bound of the premise certainty interval is a first computational function of the respective value certainty interval lower bounds, the first function being selected in the control portion. An upper bound of the premise certainty interval is the first function of the respective value certainty interval upper bounds. The inference portion fires each rule by computing a conclusion detachment interval having a lower and an upper bound, the conclusion detachment interval lower bound being a second computational function of both the rule sufficiency factor and the premise certainty interval lower bound. The conclusion detachment interval upper bounds is a third computational function of both the rule necessity factor and the premise certainty interval upper bound, the second and third functions being selected by the control portion. The conclusion detachment interval lower and upper bounds are respectively representative of the amounts of certainty and failure of refutation of the rule conclusion.
In the case where the same conclusion is provided by more than one rule in a predetermined group of rules, the inference portion is adapted to compute a conclusion aggregation certainty interval for those same conclusions. A lower bound of the conclusion aggregation interval is a fourth computation function of the conclusion detachment interval lower bounds respectively computed for the rules providing the same conclusion. An upper bound of the conclusion aggregation interval is the fourth function of the conclusion detachment interval upper bounds respectively computed for the rules providing the same conclusion. The conclusion aggregation interval lower and upper bounds are respectively representative of the amounts of certainty and failure of refutation of the aggregated conclusions. The fourth function is selected by the control portion. The inference portion is further adapted to compute a source consensus certainty interval for a plurality of the conclusion aggregation intervals for the same conclusion, where the source consensus interval is the intersection of the plurality of conclusion aggregation intervals.
The first, second and third predetermined functions comprise triangular norm (T-norm) functions which are selected from a predetermined set of T-norm functions T.sub.1, T.sub.2 and T.sub.3 by the control portion, for use by the inference portion, in computing the premise certainty and conclusion detachment intervals. Each T-norm function corresponds to a different attitude toward uncertainty evaluation. Specifically, the T-norm functions T.sub.1, T.sub.2 and T.sub.3 respectively correspond to conservative, intermediate and non-conservative attitudes toward uncertainty evaluation.
The fourth predetermined function is selected from a predetermined set of triangular conorm (T-conorm) functions S.sub.2, S.sub.2.5 and S.sub.3 by the control portion for use by the inference portion to compute the conclusion aggregation interval. Thus, the T-conorm functions S.sub.2, S.sub.2.5 and S.sub.3 are respectively selected for aggregating the same conclusions provided by uncorrelated rules, correlated rules, and rules characterized as being intermediate between positively correlated and uncorrelated.
The reasoning system described in U.S. patent application Ser. No. 103,465 overcomes problems and disadvantages in automated systems for reasoning with uncertainty. The above-described reasoning system, however, does not operate in realtime. Specifically, the knowledge base, of the above-described reasoning system is "interpreted", as opposed to compiled. "Interpreted" means that each rule of the knowledge base must be sequentially scanned, i.e. "interpreted", in order to determine whether the rule contains a variable and/or other value applicable to a task being performed. A complied knowledge base, on the other hand, is structured so that the applicability of the variables and other values are known, thereby eliminating the need to sequentially scan each rule. An analogy to the difference between an interpreted and a compiled knowledge base is the text and the topic index of a book. Without the topic index, in order to determine where a particular topic is addressed, the entire book must be scanned, i.e. interpreted. This first situation is analogous to an "interpreted" knowledge base. With a topic index, however, the exact location of where a particular topic is addressed is already known, and the reader can go directly to that location for the particular information. This second situation is analogous to a compiled knowledge base. It should be readily understood, therefore, that with the "interpreted" knowledge base of the above-described reasoning system, the time period required for the system to provide the requested information generally inhibits its real-time operation. Also, the above-described system requires a large memory space which limits the portability of the system. The required memory space prevents utilization of the system in environments having strict weight and space requirements, such as in tactical aircraft.
Moreover, in order to most effectively and efficiently operate in real-time, features which facilitate reasoning within certain time restraints are desirable. Such features include an asynchronous interface between an application program and the reasoning system and having the system recognize external and/or internal interrupts, prioritize tasks and execute tasks within a specified amount of time. Other features also are desirable for real-time operation of the reasoning system.
It is therefore an object of the present invention to provide an automated, real-time reasoning system that is not subject to the aforementioned problems and disadvantages and satisfies the requirements for real-time operation.